/**
 * @author Sebastian
 * @version 2.0
 * @date 2024/8/5 10:28
 */
// 归并排序
// 时间复杂度O（nlogn）
public class Solution912Merge {
    public int[] sortArray(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }

    private int[] mergeSort(int[] nums, int l, int r) {
        if (l == r) return new int[]{nums[l]};
        int mid = l + (r - l) / 2;
        int[] leftArray = mergeSort(nums, l, mid);
        int[] rightArray = mergeSort(nums, mid + 1, r);
        int[] newArray = new int[leftArray.length + rightArray.length];
        // 合并存进新数组
        int i = 0, j = 0, m = 0;
        while (i < leftArray.length && j < rightArray.length) {
            newArray[m++] = leftArray[i] < rightArray[j] ? leftArray[i++]:rightArray[j++];
        }
        while (i < leftArray.length)
            newArray[m++] = leftArray[i++];
        while (j < rightArray.length)
            newArray[m++] = rightArray[j++];
        return newArray;
    }

}
